package 力扣._1289_下降路径最小和;

public class Solution {
    public int minFallingPathSum(int[][] grid) {
        // t[i][j] = min(.... ,t[i-1][j-1], t[i-1][j+1]，....) + t[i][j]    //不在同一列即可
        for (int i = 1; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                //上一列非同列最小值
                int t_min = 99999999;
                for (int k = 0; k < grid[0].length; k++) {
                    if (k != j)
                        t_min = Math.min(grid[i-1][k], t_min);
                }
                grid[i][j] = t_min + grid[i][j];
            }
        }
        int min = 99999999;
        for (int j = 0; j < grid[0].length; j++) {
            min = Math.min(grid[grid.length - 1][j], min);
        }
        return min;
    }

    public static void main(String[] args) {
        //[[-73,61,43,-48,-36],[3,30,27,57,10],[96,-76,84,59,-15],[5,-49,76,31,-7],[97,91,61,-46,67]]
        int[][] grid = new int[][]{{-73, 61, 43, -48, -36}, {3, 30, 27, 57, 10}, {96, -76, 84, 59, -15}, {5, -49, 76, 31, -7}, {97, 91, 61, -46, 67}};
        int i = new Solution().minFallingPathSum(grid);
        System.out.println(i);
    }
}
